// solver_dfs.h: Header file for SolverDFS class.
// Written by Victor Luna Freire - victorclf@live.com
// Copyright (c) Victor Luna Freire. All rights reserved.
// Wednesday, October 28, 2009 2:40:46 PM

#ifndef SOLVER_DFS_H_17238719823789172893
#define SOLVER_DFS_H_17238719823789172893

#include "solver.h"

#include <list>


// Solves a maze using DFS. The solution found is not the shortest, use BFS for that.
class SolverDFS : public Solver {
	static const Vec2i UNDEFINED_PARENT_VERTEX; // the last vertex with no parent is the root.
	Vec2i cursor;
	bool backtrack;
	std::vector< std::vector<Vec2i> > parents; // each vertex parent, used to form the path in the end
	

	// Start solving. Must be private: Currently, the processed maze is altered therefore it is impossible to start solving again.
	void start_process(const Vec2i& startpos, const Vec2i& exitpos);
	// Get the parent of a vertex.
	const Vec2i& get_parent(const Vec2i& vertex) const { return parents[vertex.y][vertex.x]; };
	// Set the parent of a vertex.
	void set_parent(const Vec2i& vertex, const Vec2i& parent) { parents[vertex.y][vertex.x] = parent; };
	// Moves the cursor to the adjacent position specified. Returns false if the position is invalid!
	bool move_cursor(const Vec2i& dst);
	
public:
	// Constructs a maze solver that uses DFS.
	SolverDFS(const std::vector<std::string>& maze_to_solve, const Vec2i& startpos, const Vec2i& exitpos) 
	 	: Solver(maze_to_solve),
		  parents(h * 2 + 1, std::vector<Vec2i>(w * 2 + 1, UNDEFINED_PARENT_VERTEX))
		  { start_process(startpos, exitpos); backtrack = false; };
	
	// Perform next step in the solution. Returns false if the maze is solved. Starts solving if it was not started before.
	bool next_step();
	
	// Returns the solution found. The returned vector will be empty if no solution has been found yet.
	std::vector<Vec2i> get_solution();

	// Returns the DFS cursor position.
	Vec2i get_cursor() const { return cursor; };

	// Is backtracking?
	bool backtracking() const { return backtrack; };

	// Is the maze solved?
	bool is_done() const;
};



#endif // SOLVER_DFS_H_17238719823789172893